/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"


using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	indexHeight = 1;
	leafKeyLimit = ((PageFile::PAGE_SIZE/sizeof(int)) -2)/3;
	nonLeafKeyLimit = ((PageFile::PAGE_SIZE/sizeof(int)) -1)/2;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	if(pf.open(indexname, mode) != 0)
	{
		return RC_FILE_OPEN_FAILED;
	}
	if(pf.endPid() == 0)	//empty tree
	{
		int buffer[(PageFile::PAGE_SIZE/sizeof(int))];
		pf.write(0, buffer);
		rootPid = -1;
		indexPid = rootPid;
		treeHeight = 0;
	}
	else
	{
		BTLeafNode elRetriver;
		elRetriver.read(0, pf);
		rootPid = elRetriver.getNextNodePtr();
		indexPid = rootPid;
		treeHeight = elRetriver.getKeyCount();
	}
	//retrieve rootPid and treeHeight
	//set indexPid equal to rootPid
	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	//store rootPid and treeHeight
	int buffer[(PageFile::PAGE_SIZE/sizeof(int))];
	buffer[(PageFile::PAGE_SIZE/sizeof(int)) - 1] = rootPid;
	buffer[(PageFile::PAGE_SIZE/sizeof(int)) - 2] = treeHeight;
	pf.write(0, buffer);
	pf.close();
    return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	if(rootPid == -1)			//no root/node: empty tree
	{
		BTLeafNode initialNode;
		initialNode.insert(key, rid);
		rootPid = pf.endPid();	//intialize rootPid and treeHeight
		treeHeight = 1;
		initialNode.write(rootPid, pf);
		indexPid = rootPid;		//on constructor (or open call), indexPid must be set equal to rootPid when intialized/retrieved
		return 0;
	}
	//should be leaf node (indexHeight == 1)
	IndexCursor cursor;
	PATH.clear();				//empty the vector before calling locate
	locate(key, cursor, true);	//true -> locate will establish the PATH of parents
	indexPid = cursor.pid;
	BTLeafNode leaf;
	leaf.read(indexPid, pf);
	if(leaf.getKeyCount() < leafKeyLimit)
	{
		leaf.insert(key, rid);
		leaf.write(indexPid, pf);
		indexHeight = 1;				//reset index	//not sure it reset is neccessary
		indexPid = rootPid;
		return 0;
	}
	else
	{
		int siblingKey;
		BTLeafNode siblingLeaf;
		leaf.insertAndSplit(key, rid, siblingLeaf, siblingKey);
		int eof = pf.endPid();
		siblingLeaf.setNextNodePtr(leaf.getNextNodePtr());	//setting pointers
		leaf.setNextNodePtr(eof);
		leaf.write(indexPid, pf);
		siblingLeaf.write(eof, pf);
		return insertToParent(siblingKey, eof);	//call to a recursive function
	}
}

RC BTreeIndex::insertToParent(int key, int pid)
{
	indexHeight++;
	if(treeHeight - indexHeight < 0)	//base case: new root
	{
		BTNonLeafNode newRoot;
		newRoot.initializeRoot(indexPid, key, pid);
		rootPid = pf.endPid();
		newRoot.write(rootPid, pf);
		treeHeight++;
		indexHeight = 1;				//reset index
		indexPid = rootPid;
		return 0;
	}
	else	//get parent pid (indexPid) and insert
	{
		indexPid = PATH[treeHeight - indexHeight];
		PATH.pop_back();
		BTNonLeafNode parent;
		parent.read(indexPid, pf);
		if(parent.getKeyCount() < nonLeafKeyLimit) //2nd base case
		{
			parent.insert(key, pid);
			parent.write(indexPid, pf);
			indexHeight = 1;			//reset index
			indexPid = rootPid;
			//PATH.clear();
			return 0;
		}
		else
		{
			BTNonLeafNode sibling;
			int midKey;
			parent.insertAndSplit(key, pid, sibling, midKey);
			parent.write(indexPid, pf);
			int eof = pf.endPid();
			sibling.write(eof, pf);
			insertToParent(midKey, eof);//recursive call
		}
	}
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor, bool insert)
{
	if(rootPid == -1)
		return RC_FILE_SEEK_FAILED;	//replace with proper error code
	if(indexHeight == treeHeight)	//base case: if leaf node
	{
		BTLeafNode leaf;
		leaf.read(indexPid, pf);
		leaf.locate(searchKey,  cursor.eid);
		cursor.pid = indexPid;
		indexHeight = 1;			//reset index
		indexPid = rootPid;
		return 0;
	}
	if(insert){
		PATH.push_back(indexPid);}		//storing path for insert function
	//PATH[indexHeight-1] = indexPid;	//storing path for insert function
	indexHeight++;
	BTNonLeafNode nonLeaf;
	nonLeaf.read(indexPid, pf);
	nonLeaf.locateChildPtr(searchKey, indexPid);
	locate(searchKey, cursor, insert);		//recursion
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	if(cursor.pid==-1) //end of tree case
	{
        return RC_END_OF_TREE;
    }
	BTLeafNode leaf;
    leaf.read(cursor.pid, pf);
    leaf.readEntry(cursor.eid, key, rid);
    int count = leaf.getKeyCount();

    // Case where we need to get next node pointer
    if(cursor.eid == count) {	//changed!!!
        cursor.pid = leaf.getNextNodePtr();
        cursor.eid = 0;
    } else {
        cursor.eid++;
    }

    return 0;
}
